package leetcode.hot100;

@SuppressWarnings("all")
public class _0_1背包 {

    public static int maxValue(int[] values, int[] weights, int capacity) {
        // 没有物品可以选
        if (values == null || values.length == 0) return 0;
        // 没有容量可以装
        if (weights == null || weights.length == 0) return 0;
        // 一件物品必然要对应一个份重量
        if (values.length != weights.length || capacity <= 0) return 0;
        // dp[i][j]表示最大承重为j时，有前i件物品可以选择时能够获取的最大价值
        int[][] dp = new int[values.length + 1][capacity + 1];
        // 至少得有一件物品，至少背包容量要为一
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                // 如果当前背包的容量不足以容纳当前物品，那么背包所拥有的最大价值还是选择前(i-1)件物品时的最大价值
                if (j < weights[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 选择第i件物品与不选择第i件物品所获取的最大价值比较
                    dp[i][j] = Math.max(
                            dp[i - 1][j],
                            values[i - 1] + dp[i - 1][j - weights[i - 1]]);
                }
            }
        }
        return dp[values.length][capacity];
    }
}
